﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution174
{
    public int CalculateMinimumHP2(int[][] dungeon)
    {

        int m = dungeon.Length;
        int n = dungeon[0].Length;
        int[][] dp= new int[m][];
        for (int i = 0; i < m; i++)
        {
            dp[i]= new int[n];
        }
        dp[0][0] = dungeon[0][0];
        for (int i = 1;i < n; i++)//第一行只能从左边过来
        {
            dp[0][i]= dp[0][i-1]+dungeon[0][i];
        }

        for (int j = 1; j < m; j++)//第一列只能从上边过来
        {
            dp[j][0] = dp[j-1][0] + dungeon[j][0];
        }
        for(int i = 1; i < m; i++)
        {

            for (int j = 1; j < n; j++)
            {
                //不是越少越好，选择最大的负数

                if(dp[i - 1][j]<0&& dp[i][j - 1] < 0)
                {
                    dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1]) + dungeon[i][j];
                }else if (dp[i - 1][j] < 0 && dp[i][j - 1] > 0)
                {
                    dp[i][j] = dp[i - 1][j]  + dungeon[i][j];
                }else if (dp[i - 1][j] > 0 && dp[i][j - 1] < 0)
                {
                    dp[i][j] = dp[i][j - 1] + dungeon[i][j];
                }
                else//前面两个都是正血量
                {
                    dp[i][j] = dungeon[i][j];
                }


                if (dp[i][j] <= 0)
                {
                    //这条路不通
                }

                
            }

        }

//最后还有多余的血，说明中间加了很多，
        
            return -dp[m - 1][n - 1] + 1;
        

        

    }

    //考虑后面的路线消耗的血量，选择较小的进行
    public int CalculateMinimumHP(int[][] dungeon)
    {

        int m = dungeon.Length;
        int n = dungeon[0].Length;
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++)
        {
            dp[i] = new int[n];
        }

        if(dungeon[m - 1][n - 1] >= 0)
        {
            dp[m - 1][n - 1] = 0;//来之前血量为1就可以
        }
        else
        {
            dp[m - 1][n - 1] = -dungeon[m - 1][n - 1];
        }
       
        for (int i = m-2; i >= 0; i--)//最后一列只能从下边过来
        {
            dp[i][n - 1] = Math.Max(0, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        
        }

        for (int j = n-2; j >= 0; j--)//最后一行只能从右边过来
        {
            Console.WriteLine(j);
            dp[m-1][j] = Math.Max(0, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }
        for (int i = m - 2; i >= 0; i--)
        {

            for (int j = n - 2; j >= 0; j--)
            {
                //不是越少越好，选择最大的负数
                //来当前格子之前需要的血量是，后面路线需要的+当前格子需要的


                if (Math.Min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j] <= 0)
                {
                    dp[i][j] = 0;
                }
                else
                {
                    dp[i][j] = Math.Min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                }

            }

        }

        //最后还有多余的血，说明中间加了很多，

        return dp[0][0]+1;




    }
}

class Program174
{
    static void Main174(string[] args)
    {
        Solution174 solution = new Solution174();
        

        //int[][] dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]];
        int[][] dungeon = [[0,0]];
      int res=  solution.CalculateMinimumHP(dungeon);
        Console.WriteLine(res);
    }
}
